// https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/lian-biao-jie-dian-jiao-huan-by-jackwang86/
// 给定 1->2->3->4, 你应该返回 2->1->4->3.

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *pre = NULL;
        ListNode *p1 = head;
        ListNode *p2 = NULL;
        ListNode *new_head = NULL;

        while (p1 && p1->next)
        {
            // 1. 先取出 p1 下一个节点
            p2 = p1->next;

            /**
                2. 先交换 p1 与 p2
                1 -> 2 -> 3 ====> 2 -> 1 -> 3
                - 1) 1 指向【2】的【下一个】元素【3】
                - 2) 2 指向 1
             */
            p1->next = p2->next;
            p2->next = p1;

            // 3. 区分是否是【第一次】交换操作
            if (pre == NULL)
            {
                /**
                 *  1 -> 2 -> 3
                 *  |    |
                 *  p1   p2
                 *
                 * p2 作为新的链表【头节点】
                 */

                if (new_head == NULL)
                    new_head = p2;
            }
            else
            {
                /**
                 *  1 -> 2 -> 3
                 *  |    |    |
                 *  pre  p1   p2
                 *
                 * p2 作为 pre 指向节点的【下一个】节点
                 */

                pre->next = p2;
            }

            // pre 往后移
            pre = p1;

            // p1 移动到下一个节点
            p1 = p2;
        }

        return new_head;
    }
};
